package com.crab.c04tree;

import java.util.Arrays;

/**
 * 二叉堆  分最大堆最小堆，是堆排序和优先队列的基础
 * 底下用户数组实现，parent的索引pIdx位置可以确定孩子的索引位置:
 * lIdx = 2 * pIdx +1
 * rIdx = 2 * pIdx +2
 * <p>
 * 以最小堆为例， 常用操作：
 * 1、新增：在数组最后插入元素，然后该元素做“上浮”，logn复杂度
 * 2、删除：将数组元素交换到删除的位置，然后该元素做做“下沉”，logn复杂度
 * 3、构建堆：无序的完全二叉树调整为二叉堆，本质是让所有非叶子节点(从下往上找非叶子)依次“下沉”，
 *
 * @author zfd
 * @version v1.0
 * @date 2022/4/29 8:51
 */
public class BinaryHeap {

    public static void main(String[] args) {
        int[] array = new int[]{1,2,3,9,10,8,7,5,6};
        buildHeap(array);
        System.out.println(Arrays.toString(array));

        // upAdjust(array);
        // System.out.println(Arrays.toString(array));
    }

    /**
     * 构建堆
     *
     * @param array
     */
    public static void buildHeap(int[] array) {
        // 从最后的非叶子节点开始，依次下沉
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
    }


    /**
     * 下沉调整
     *
     * @param array       待调整的堆
     * @param parentIndex 要下沉的父节点的索引
     * @param length      堆大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        // 待下沉的节点的值，用于比较和最后直接赋值，中间交换直接覆盖即可
        int temp = array[parentIndex];
        // 要交换的孩子的索引 可能是左也可能右
        int childIndex = parentIndex * 2 + 1; // 左
        while (childIndex < length) {
            // 取左右孩子最小值
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++; // 右
            }
            // 如果父小于任何一个孩子的值 直接跳出
            if (temp <= array[childIndex]) {
                break;
            }

            // 不交换 单向赋值
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        // 下沉完毕赋值
        array[parentIndex] = temp;
    }

    /**
     * 插入新元素 做上浮操作
     * 假设数组中的最后一个元素已经刚插入的新元素，做上浮调整
     *
     * @param array
     */
    public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        // 插入的叶子节点值 用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        // 赋值
        array[childIndex] = temp;
    }
}
